package org.cabbage.lintcode;

import java.util.LinkedList;
import java.util.List;

/**
 * 给定两个值 k1 和 k2（k1 < k2）和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节点。
 * 即打印所有x (k1 <= x <= k2) 其中 x 是二叉查找树的中的节点值。返回所有升序的节点值。
 *
 * @author gezhangyuan
 */
public class SearchBTree {

    List<Integer> list = new LinkedList<Integer>();

    public static void main(String[] args) {

    }

    public void search(TreeNode node, int k1, int k2) {
        if (node.left != null && node.val > k1) {
            search(node.left, k1, k2);
        }
        if (node.val >= k1 && node.val <= k2) {
            list.add(node.val);
        }
        if (node.right != null && node.val < k2) {
            search(node.right, k1, k2);
        }
    }

    public List<Integer> searchRange(TreeNode root, int k1, int k2) {
        if (root == null) {
            return list;
        }
        search(root, k1, k2);
        return list;
    }
}
